/*
*
* 二分查找
* 主要思想：将数组（已排序）一直二分缩小范围，直到找到为止
* */

function quickSort(arr,left,right){{
    if (left >= right){
        return arr;
    }
    let value = arr[left];
    let i = left;
    let j = right;
    while(i < j){
        while(j > i && arr[j] >= value){
            j--;
        }
        while(i < j && arr[i] <= value){
            i++;
        }
        if (i < j){
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[left] = arr[i];
    arr[i] = value;
    quickSort(arr,left,i - 1);
    quickSort(arr,i + 1,right);
    return arr;
}}
/*
let array = quickSort([1,2,3,423,123,32,1],0,6);
console.log(array)*/

function binarySearch(arr,item){
    let array = quickSort(arr,0,arr.length - 1);
    let mid = Math.floor((0 + array.length - 1)/2);
    let i = 0;
    let j = array.length;
    while(i < j){
        if (array[mid] > item){
            j = mid - 1;
        }else if(array[mid] < item){
            i = mid + 1;
        }else{
            return mid
        }
        mid = Math.floor((i + j)/2);
    }
    return -1;
}

let binary = binarySearch([1,23,43,23,12,23,34,3,23,43],12);
console.log(binary);
